﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class ListNode
{
    public int val;
    public ListNode next;
    public ListNode(int val=0, ListNode next=null)
    {
        this.val=val;
        this.next=next;
    }

}
public class Solution206
{
    //迭代法
    public ListNode ReverseList1(ListNode head)
    {

        ListNode newhead= null;  
        //newhead.next=null;
        ListNode pre = new ListNode();  
        ListNode cur = head;  
        
        while (cur != null) {
            pre = cur;
            cur = cur.next;
            pre.next = newhead;
            newhead = pre;
                }
        return newhead;
    }

    //递归法
    public ListNode ReverseList(ListNode head)
    {

        if (head == null | head.next == null)
        {
            return head;
        }

        ListNode newhead = ReverseList(head.next);
        head.next.next = head;//这里的head是递归帮忙记住的
        head.next = null; 
        return newhead;
    }
}
class Program206
{


    static void Main206(string[] args)
    {
        ListNode head = null; // 头节点

        ListNode current = null; // 当前节点

        // 使用尾插法建立链表
        for (int i = 1; i <= 10; i++)
        {
            ListNode newNode = new ListNode(i); // 创建新节点

            if (head == null) // 如果是第一个节点
            {
                head = newNode;
                current = newNode;
            }
            else
            {
                current.next = newNode; // 将当前节点的 next 指向新节点
                current = current.next; // 更新当前节点为新节点
            }
        }

        current.next = null; // 将最后一个节点的 next 设置为 null

        // 遍历链表并输出节点的值
        ListNode node = head;
        while (node != null)
        {
            Console.WriteLine(node.val);
            node = node.next;
        }

        Solution206 solution = new Solution206();
        ListNode newnode =solution.ReverseList(head);
        while (newnode != null)
        {
            Console.WriteLine(newnode.val);
            newnode = newnode.next;
        }
        Console.ReadKey();
        




    }

}


